Exercise (Week 6)

We define a Token as either a number or a binary operator:

data Token = Number Int | Operator (Int -> Int -> Int)

First, we need a way to translate String values into proper calculable expressions, that is, lists of Token. We have already defined a function that will attempt to convert a single word into a single Token, called parseToken:

parseToken :: String -> Maybe Token
parseToken "+" = Just (Operator (+))
parseToken "-" = Just (Operator (-))
parseToken "/" = Just (Operator div)
parseToken "*" = Just (Operator (*))
parseToken str = fmap Number (readMaybe str)

Your first task is to implement the function tokenise:

tokenise :: String -> Maybe [Token]

This function must break the string into words (the built-in words function will be useful), and then attempt to parse each one into a Token, returning a non-Nothing result only if every word can be parsed.

Note that you can (and should) exploit the fact that Maybe is an instance of Monad, Applicative and Functor. This will enable you to make the above function into a short, one-line definition.

Next, in order to evaluate RPN expressions, we need a convenient way to model computations which manipulate a stack, and can possibly fail (for example, if we were to try to pop from an empty stack).

In Haskell, such a computation could be modelled as a function that, given an input stack (of Int), will either fail (returning Nothing) or return Just an output stack with an additional return value.

newtype Calc a = C ([Int] -> Maybe ([Int], a))

Implement the two basic stack operations, push and pop as Calc computations.

pop  :: Calc Int
push :: Int -> Calc ()

We have provided instances of Monad, Applicative and Functor for Calc:

instance Functor Calc where
  fmap f (C sa) = C $ \s ->
      case sa s of
        Nothing      -> Nothing
        Just (s', a) -> Just (s', f a)

instance Applicative Calc where
  pure x = C (\s -> Just (s,x))
  C sf <*> C sx = C $ \s ->
      case sf s of
          Nothing     -> Nothing
          Just (s',f) -> case sx s' of
              Nothing      -> Nothing
              Just (s'',x) -> Just (s'', f x)

instance Monad Calc where
  return = pure
  C sa >>= f = C $ \s ->
      case sa s of
          Nothing     -> Nothing
          Just (s',a) -> unwrapCalc (f a) s'
    where unwrapCalc (C a) = a

All three instances make sure that the whole computation will return Nothing if any subcomputation returns Nothing. Furthermore, the Applicative and Monad instances allow us to thread the stack through multiple computations without manually keeping track of this state. For example, the Calc computation that adds the two topmost elements of the stack and pushes the result back to the stack can be defined as:

addTwo :: Calc ()
addTwo = do
  x <- pop
  y <- pop
  push (x + y)

By threading the stack through in the Monad instance here, we can just treat the stack as some implicit state that we manipulate abstractly with Calc computations. This allows us to make code much shorter and cleaner.

Using the above instances for Calc, define a function evaluate:

evaluate :: [Token] -> Calc Int

This should evaluate a list of Token as described above, using the stack operations you defined earlier, finally returning the topmost element of the stack.

Lastly, define a function calculate:

calculate :: String -> Maybe Int

That will first attempt to parse the given string with tokenise to get a list of tokens. If that succeeds, it should use evaluate to get a Calc computation corresponding to that list of tokens. Then, it should run that computation starting with an empty stack, returning just the resultant integer from that computation, if any. If the stack has more than one element when calculate runs, it should return the topmost element.

Note that once again you can use the Monad, Applicative and Functor instances of Maybe to succinctly implement this function.

After implementing this function, test it with the examples listed at the beginning of this exercise, and try your own examples also.